#include <dbg.h>
#include <gtest/gtest.h>

#include <cmath>
using namespace std;

class Solution {
public:
    int visiblePoints(vector<vector<int>>& points,
                      int angle,
                      vector<int>& location) {
        int sameCnt = 0;

        vector<double> polarDegrees;  // 极角数组
        for (auto& point : points) {
            if (point == location) {
                ++sameCnt;  // 记录与 location 相同的点
                continue;
            }
            double x = atan2(point[1] - location[1], point[0] - location[0]);
            polarDegrees.push_back(x);
        }
        sort(polarDegrees.begin(), polarDegrees.end());
        dbg(polarDegrees);

        int m = polarDegrees.size();
        for (int i = 0; i < m; ++i) {
            polarDegrees.push_back(polarDegrees[i] +
                                   2 * M_PI);  // 复制一份加上 2π
        }
        dbg(polarDegrees);

        int maxCnt = 0;
        int right = 0;
        double degree = angle * M_PI / 180;  // 角度转弧度
        for (int left = 0; left < m; ++left) {
            while (right < polarDegrees.size() &&
                   polarDegrees[right] <= polarDegrees[left] + degree) {
                ++right;
            }
            maxCnt = max(maxCnt, right - left);  // 计算窗口内的点数
        }
        return sameCnt + maxCnt;
    }
};

TEST(TEST1, visiblePoints) {
    Solution s;

    vector<vector<int>> points = {{2, 1}, {2, 2}, {3, 3}};
    int angle = 90;
    vector<int> location = {1, 1};
    EXPECT_EQ(s.visiblePoints(points, angle, location), 3);
}

TEST(TEST2, visiblePoints) {
    Solution s;

    vector<vector<int>> points = {{2, 1}, {2, 2}, {3, 4}, {1, 1}};
    int angle = 90;
    vector<int> location = {1, 1};
    EXPECT_EQ(s.visiblePoints(points, angle, location), 4);
}

TEST(TEST3, visiblePoints) {
    Solution s;

    vector<vector<int>> points = {{1, 0}, {2, 1}};
    int angle = 13;
    vector<int> location = {1, 1};
    EXPECT_EQ(s.visiblePoints(points, angle, location), 1);
}

TEST(TEST4, visiblePoints) {
    Solution s;

    vector<vector<int>> points = {{-1, -1}, {1, -1}, {1, 1}, {-1, 1}, {0, 2}};
    int angle = 90;
    vector<int> location = {0, 0};
    EXPECT_EQ(s.visiblePoints(points, angle, location), 3);
}

int main(int argc, char* argv[]) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}